#include "ACAutomation.hpp"
#include <queue>
#include <unordered_map>
#include <iostream>

TrieNode::TrieNode(char key)
    : keyChar(key)
    , isMatch(false)
    , pattern()
    , fail(nullptr)
    , father(nullptr)
{
    for (int i = 0; i < CHARNUMS; ++i)
    {
        next[i] = nullptr;
    }
}

ACAutomation::ACAutomation()
    : dict_()
    , ready(false)
    , firstInit(true)
{
    root_ = new TrieNode();
}

ACAutomation::ACAutomation(std::unordered_set<std::string> patternSet)
{
    for (auto& p : patternSet)
    {
        insertPattern(p);
    }
    initFailPointer();
}

ACAutomation::~ACAutomation()
{
    if (firstInit) //如果还没用过，就直接返回吧
    {
        return ;
    }
    cleanUp(root_);
}

void ACAutomation::matchText(const std::string& text)
{
    checkReady();
    std::cout << "matching pattern:\n" << text << std::endl;
    std::unordered_map<std::string, int> result;
    TrieNode* curNode = root_;
    for (int i = 0; i < text.size(); ++i)
    {
        if (curNode->next[text[i] - 'a'])
        {
            curNode = curNode->next[text[i] - 'a']; //子节点非空往下走
        }
        else
        {
            curNode = curNode->fail; //子节点空找fail指针
        }

        if (curNode->isMatch)
        {
            result[curNode->pattern] += 1; //独立成词加入结果缓存
        }
    }

    if (result.empty()) //没匹配到，礼貌返回
    {
        std::cout << "No Match for text:\n" << text << std::endl;
        return ;
    }

    for (auto& kv : result)
    {
        std::cout << "Found " << kv.first << " : "
                  << kv.second << " times.\n";
    }
}

void ACAutomation::removePattern(const std::string& pat)
{
    if (dict_.find(pat) == dict_.end())
    {
        std::cerr << "Pattern: " << pat << " not included in ACAutomation\n";
        return ;
    }
    dict_.erase(pat); //先从字典缓存中删除
    removePattern(root_, pat, 0); //删除字典树中的节点
    ready = false;
}

void ACAutomation::insertPattern(const std::string& pat)
{
    if (dict_.find(pat) != dict_.end())
    {
        return ; //pattern串已存在，直接返回，不改动ready状态
    }
    TrieNode* curNode = root_;
    for (int i = 0; i < pat.size(); ++i)
    {
        TrieNode* nextNode = curNode->next[pat[i] - 'a'];
        if (nextNode == nullptr)
        {
            curNode->next[pat[i] - 'a'] = new TrieNode(pat[i]);
            nextNode = curNode->next[pat[i] - 'a'];
            nextNode->father = curNode;
        }
        curNode = nextNode;
    }

    curNode->pattern = pat;
    std::cout << "put " << pat << " in acautomation\n";
    curNode->isMatch = true;
    dict_.insert(pat);
    ready = false; //lazy evaluation 标记当前AC自动机未就绪，在查询之前，需要重建fail指针，不必每次插入都重建
}

bool ACAutomation::lookupPattern(const std::string& pat)
{
    return dict_.find(pat) != dict_.end();
}

void ACAutomation::cleanUp(TrieNode* root)
{
    for (int i = 0; i < CHARNUMS; ++i)
    {
        if (root->next[i] != nullptr)
        {
            cleanUp(root->next[i]);
            root->next[i] = nullptr;
        }
    }
    delete root;
}

void ACAutomation::clearFailPointer(TrieNode* root)
{
    for (int i = 0; i < CHARNUMS; ++i)
    {
        if (root->next[i] != nullptr)
        {
            clearFailPointer(root->next[i]);
        }
    }
    root->fail = nullptr;
}


void ACAutomation::removePattern(TrieNode* root, const std::string& pat, int ind)
{

    if (pat[ind] == '\0')
    {
        root->isMatch = false; //已达字符串末尾，将成词标志改为false
    }
    else
    {
        removePattern(root->next[pat[ind] - 'a'], pat, ind + 1);
    }

    if (!root->isMatch)
    {
        for (int i = 0; i < CHARNUMS; ++i)
        {
            if (root->next[i]) //如果存在子节点，那就返回
            {
                return ;
            }
        }
        //执行到这说明所有子节点均为nullptr，可以删除此节点了
        root->father->next[pat[ind] - 'a'] = nullptr;
        delete root;
    }
    return ;
}

void ACAutomation::checkReady()
{
    if (ready)
    {
        return ;
    }

    if (firstInit)
    {
        initFailPointer();
        firstInit = false;
        return ;
    }

    rebuildFailPointer();
    ready = true;
}

void ACAutomation::rebuildFailPointer()
{
    if (ready) //如果已经就绪，无须重建
    {
        return ;
    }
    clearFailPointer(root_);
    initFailPointer();
}

void ACAutomation::initFailPointer()
{
    std::queue<TrieNode*> q;
    root_->fail = root_;
    for (int i = 0; i < CHARNUMS; ++i) //首先初始化root_节点下的子节点fail指针
    {
        if (root_->next[i])
        {
            q.push(root_->next[i]);
        }
    }

    while (!q.empty()) //开始层序遍历
    {
        TrieNode* curNode = q.front();
        q.pop();

        for (int i = 0; i < CHARNUMS; ++i)
        {
            if (curNode->next[i]) //如果存在子节点，加入层序遍历队列
            {
                q.push(curNode->next[i]);
            }
        }

        TrieNode* failCursor = curNode->father->fail;
        bool matchFail = false;
        bool passRoot = false;
        while (failCursor != root_ || !passRoot)
        {
            if (failCursor == root_) //第一层肯定会经过root点，以此标记，防止无限循环
            {
                passRoot = true;
            }

            TrieNode* matchNode = failCursor->next[curNode->keyChar - 'a'];
            if (matchNode && matchNode != curNode)
            {
                curNode->fail = matchNode; //在fail链上匹配到了合适的keyChar作为fail的下一跳
                matchFail = true;
            }
            //如果匹配到下一跳fail指针，则退出while循环
            if (matchFail)
            {
                break;
            }
            //如果未找到合适的fail指针，继续沿着fail链上遍历
            failCursor = failCursor->fail;
        }

        if (!matchFail) //如果退出while循环的原因不是因为找到下一跳的情况，说明找不到下一跳，将当前节点fail指针置为root_
        {
            curNode->fail = root_;
        }
    }
    //初始化结束，ac自动机可以开始匹配了
    ready = true;
}